Lecture 1.1: Introduction to Zero Knowledge

2019年BIU密码学冬令营Zero Knowledge, lecture by Alon Rosen recorded by Yu-sheng Zhao

Zero-knowledge proofs

下列粗犷的给出了零知识证明的定义

ZKP可以表示为两个实体之间的互动（an interaction between the two entities）

• 证明方Proof $P$
• 验证方Verifier $V$
• $P$和$V$做互动，$P$尝试说服$V$让后者相信某个断言为真
• 这一交互行为除了“该断言为真”这一事实之外并无其他信息

ZKP的非互动的形式：

If proposition is true，any $V^*$ might as well have generated（simulated） the interaction on his own

任一$V^*$都可以和自己进行交互，从而获得某一真（true）断言。（没有从互动中学习到任何额外的信息）

ZKP的高明之处在于通过定义“zero knowledge”，回避了“what is knowledge？”这个问题，后者显而易见是一个不好回答的哲学问题。zero knowledge的定义可以表述为：it means for knowledge not to be leaked without defining what knowledge is（没有知识的定义就没有知识的泄露）

ZK的一个经典例子： 如何让色盲相信两个小球的颜色不同（color non-blindness）

验证方$V$即色盲，证明方$P$试图说服$V$其手上的两个球颜色是不同的。假设$V$左右手分别持有绿色球和红色球：

每次交互，$V$选择是否交换（swap）手中的球，然后询问$P$是否交换

如果$V$完全信任$P$的回复，则理想状态下每次$P$都能回复正确答案。

证明方告知验证方轮询结果，这也是交互过程的一部分。在这个过程中每一次质询反馈结果验证方都能即时判断证明方回答是否正确。

通常情况下，$V$不应当信任$P$。即假设$P$的回答是随机的，每一轮质询都有$\frac{1}{2}$概率回答正确。经过$n$轮质询后，回答正确的概率等于$\frac{1}{2}^n$，当质询次数足够多，证明方每次都猜对，$P$的置信度趋近于1，这时$P$可以完成针对该断言的零知识证明。在整个过程中，证明方未向验证方透露出除该断言判断（是否交换）以外的信息。

$V$的视角：a random bit that equals his “swap or not” bit——通过随机选择比特位（0 or 1）来自行模拟该过程

ZK的初步应用

ZK可以证实我所知晓的一个secret而不暴露（reveal）它。它可以用于以下两个方面：

• *身份认证「Identification」：举例来说，Alice有一函数$y=f(x)$，假设一些random secret使得$f$很难求反，即$f^{-1}$是困难问题（给定$y$不好求$x$），在ZK语境下，Alice可以通过向Bob证明她知道$x^{'}\in f^{-1}(y)$从而向Bob认证Alice的身份

• *协议设计「Protocol design」：

  在Protocol design中，应用ZK使设计安全的协议有了可能，使其不受恶意攻击。为了让我们的协议不受那些恶意的或半诚实的攻击（非法或合法尽可能获取更多的知识），我们应用零知识证明，把Protocol design过程分为两步走：

  • 设计的一部分（一个）协议，假设这个协议是follow instructions的，这个协议做了它们应该做（supposed to do）的事，即ZK针对遵循的当事人进行设计。
  • 用零知识来compile这个协议，为了让生成协议不对原始协议产生偏差，我们的方法是在模型中运行原始协议（original protocol），在这个模型中，我们假设一方（party）遵循协议，并且force该方做零知识证明，证明“己方遵循了协议”。使用零知识证明可以促成一些诚实的行为。

  

  （原PPT是这两句话，赶脚一知半解:-)

如果我们的视野够长远，所有application的knowledge都fall into在整个框架中。我们可以从一个假设：“我们有一个trusted party”出发，去构建一个比零知识更普适的通用密码学框架，其能够执行所有我们预设的操作，然后基于ZK来获取一个完整的加密协议。总而言之，ZK可以让我们从一个信任的环境走向（更广阔的）不信任的环境。

WHY zero-knowledge？

• ZK可以是一个Remarkable definitional framework（优质的可定义框架）

  • At the heart of protocol design and analysis
  • Brings to light key concepts and issues

  ZK处于协议设计和分析的核心地位，当我们了解了协议中的零知识，也就知晓了协议的基本定义。在设计协议的时候，ZK可以让我们用更简洁更优雅的方式来考虑所有问题（cast all sorts of consideration），研究ZK很有意义，ZK给了很多关键的概念和想法。

• Right level of abstraction: （不错的）

  • Simple enough to be studied/realized: ZK处于一个很好的抽象层次：ZK足够简单、足够包容，以至于我们甚至在学校就可以完成了解、学习和真正实现它（understand、study、realize）的一个过程
  • Feasibility/limitations delineate what is attainable:
    如果证明了某个知识不能适用于某些事务，这项结论可以拓展到其他事务上。

综上所述，ZK非常简洁，不仅足够inclusive，而且也展示了ZK的可行性（feasibility）。同时，ZK可以表达“零知识”，即“things are impossible is knowledge”，也将会贯彻到（carry through）Crypto Dust。

迷糊 解释Crypto Dust待拔草

ZK虽然处于一种Right level of abstraction，但并不像图灵机，它仅仅是一种手段（mean to an end），只是一个工具（tool），它也有无能为力的时候。There is nothing holy about ZERO!：）

• Weaker definitions are also useful(WI/WH/NIZK) 这种较弱的对ZK的定义往往并没有泄露knowledge，而是承认（acknowledge）一些useless knowledge——在这种场景witness distinguish ability with deciding on interactive zero knowledge
• Tension between modularity and efficiency: ZK可以使我们去模块化协议设计。把ZK相关的部分当做一个magic box，使得在没有ZK定义的前提下，我们可以实现一个系统并使用其相关knowledge。在另一方面，如果我们想要实现（implement）某些东西，ZK中的what we learn就是我们的绊脚石，我们最好了解ZK的内部运作方式，如果我们想implement efficiently，我们就必要了解其内部工作原理。

Proof System

proof（证明）的定义/意味

proof是一种建立真相（truth）的方法（methods）。证明或者这种方法具体的意味取决于证明所使用的环境。

proof可以是（e.g.）法律、权威、科学方法、哲学方法、数学方法…

上图描述了一个经典的论证过程：从公理出发，经过一系列推导验证，得到一个命题，这个命题往往非真即假。为了不从正确的假设推导出错误的断言，我们在证明的概念增加了两个要素：probabilistic以及interactive

Proof Systems（证明系统）

给出一例子：在特定环境下，证明一些输入或实例行为（$x$）属于一种语言（$L$）。形式化描述如下

在这个过程中，证明者无关紧要，而验证者（verifier）则是证明过程中最重要的实体（entity），这条结论同样适用于设计并实现协议的个体。如果从证据的可靠性出发，这条结论也是显而易见的。

证明系统的定义

我们给定$L$表示所有字符串行为的集合，验证者给定$x$，经过证明系统（一系列操作抑或证明方法$\pi$）得出输出$V(x,\pi)$，要求该输出为真（即accept）。我们可以记作$L=\{x |\exist \pi,V(x,\pi)=ACCEPT\}$

抽象化以上过程，我们给出对于$L$中所有成员的证明系统是一个算法$V$使得对任意的成员$x$（或断言），满足

• 完备性（Completeness）：如果$x \in L$，则$\exist \pi$，使得$V(x,\pi)=ACCEPT$
• 可靠性（Soundness）：如果$x \notin L$，则$\exist \pi$，使得$V(x,\pi)=REJECT$

以上是证明（proof）的两个主要性质。

NP证明系统

观点：只在我们有生之年可以被验证的断言是有价值/意义的

因此，一个有效的验证（efficient verification）等价于一个可以在多项式时间内完成的验证（poly-time verification）。显然地，时间复杂度越低，验证效率越高。

给出NP证明系统的定义如下：

我们给出对于$L$中所有成员的NP证明系统是一个算法$V$使得对任意的成员（或断言）$x$，满足

• 完备性（Completeness）：如果$x \in L$，则$\exist \pi$，使得$V(x,\pi)=ACCEPT$
• 可靠性（Soundness）：如果$x \notin L$，则$\exist \pi$，使得$V(x,\pi)=RELECT$
• 效率（efficiency）：验证环节至多在$poly(|x|)$步内完成

关于第三条性质，附加一些解释：算法$V$的运行时间由$|x|$（即$x$的尺寸）来衡量；满足$poly(|x|)=|x|^c$，其中$c$为常数，不随$|x|$变化而变化；证明方法的尺寸应当等于多项式时间$|\pi|=poly(|x|)$。综上，相比证明系统的定义，NP证明系统的定义更强，给出了在算法效率方面的限制。

例子1：布尔可满足性（Boolean Satisfiability）

布尔可满足性：对于某个布尔公式，是否存在一组布尔值的输入，使得这个布尔公式的结果为 True。如果存在，则称这个布尔公式为布尔可满足的。

$SAT$是布尔可满足公式$\phi$的集合，表示为$SAT = \{ \phi(w_1,w_2,\dots,w_n)|\exist w\in \{0,1\}^n,\phi(w)=1 \}$。那么如何证明该集合是合法的呢？只需要将赋值发送给验证者，然后验证者将公式代入值，对其进行评估，判断结果是真或假。

只有有证据（witness），验证方就可以轻易验证该证明。

• 复杂性（Complete）：每个语言$L\in NP$都可以归约到$SAT$ 这个性质的解释：$SAT$是$NPC(Complete)$ 问题,每一个$NP$问题（即语言$L\in NP$）都可以规约到$SAT$问题上。
• 非结构化（Unstructured）：算法的最差表现——时间复杂度为$exp(\mathcal{O}(n))$ 我们不知道任何有效的通用的算法来决定$SAT$这种非结构化问题，因此虽然我们了解该算法的最坏表现（时间随着规模变化指数增长），但我们并不了解算法的平均表现，也不了解在某些分布下的随机实例化的结果。不过我们了解每种算法都有一个适合其的实例化问题。

例子2：线性方程组的求解（Linear Equations）

$LIN$是在$\mathbb{F}$上有解的线性方程组$(A,b)$的集合，记作$LIN = \{(A,b)|Aw=b \ ℎ𝑎𝑠 \ 𝑎 \ 𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 \ 𝑜𝑣𝑒r\ \mathbb{F}\}$。类似例子1，发送一个解给验证方，然后做矩阵向量乘法看看其是否满足线性方程组。

• 非结构化（Unstructured）：时间复杂度是确定的，为$\mathcal{O}(n^{2.373})=ploy(n)$ 这个值2.373（Alon说）是最快的两个矩阵相乘的算法的指数。

P类问题

如上所述，我们用多项式时间（poly-time）复杂度的算法来确定该算法的高效程度，即$poly-time \ <=>\ efficient$

P问题的定义：在多项式时间（poly-time）复杂度的算法$A$下，有$L\in P$，使得$L=\{x|A(x)=ACCEPT\}$。

如上图所示，例子1中的$SAT$是$NPC$问题，例子2的$LIN$是一个$P$问题

涉及到三类问题：P、NP、NPC这三者的定义和区别👇

• P类问题在多项式时间内有解。其描述为一类“确定性图灵机”，执行路径对于输入$x$是一个线性的状态转移。（多项式时间内可以求解的复杂类）
• NP类问题在多项式时间下不能确定能找到解，但在多项式时间下可验证解的正确性。其描述为一类“不确定性图灵机”，即它每往前走一步是不确定的，有很多个选择，只要任何一个执行路径能到达终止状态，就表示它解决了该问题$x$。（多项式时间可以求解的问题类）
• NPC类问题定义为在这样的NP问题上——NP中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间的算法，那么所有NP问题都是多项式时间可解的。这些问题被称为NP-完全(NPC)问题，NP类问题都可以reduce到一个NPC类问题（例如SAT）。

Alon这里也提及了BPP类问题，这是一类在多项式时间内被概率图灵机（即概率的多项式时间「probabilistic poly-time (𝑃𝑃𝑇) 」算法）解出的问题，并且对所有的输入，输出结果有错误的概率差不多是1/3。P类问题是错误概率为0时的BPP类问题。BBP类问题当作是P类问题的概率化扩展。以下例子3就是一类BPP问题。

例子3：二次剩余问题（Quadratic Residuosity）

$QR_N$是模$N$的二次剩余类的集合，记作$QR_N=\{x|x \ is \ a \ quadratic\ residue \ mod \ N \}$。需证明问题如下

这是一个NP问题，我们只需要发送平方根给验证者，让其验证

• 结构化（Structured）：$QR_N$是集合$\Z^*_N$的一个子群（subgroup）
• 对于$𝑁 = 𝑃𝑄(|𝑃| = |𝑄| = 𝑛)$，平均时间复杂度：$exp(\tilde{O}(n^{\frac{1}{3}}))$←平均最好时间只能如此，这可能是一个很难解决的问题

第一节听的稀里糊涂的：：😔